﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    public class RationalPath
    {
        private int rationalPathCount = 0;
        public RationalPath()
        {
            int pointCount = GetConsole.GetInt();
            int pathCount = GetConsole.GetInt();
            Dictionary<int, PointInfo> pointDic = new Dictionary<int, PointInfo>();
            while (pathCount-- > 0)
            {
                int indexA = GetConsole.GetInt();
                int indexB = GetConsole.GetInt();
                int length = GetConsole.GetInt();
                if (!pointDic.ContainsKey(indexA))
                {
                    pointDic.Add(indexA, new PointInfo());
                }
                if (!pointDic.ContainsKey(indexB))
                {
                    pointDic.Add(indexB, new PointInfo());
                }
                pointDic[indexA].AddPath(indexB, length);
                pointDic[indexB].AddPath(indexA, length);
            }
            pointDic[2].LengthToEnd = 0;
            FindPath(pointDic[2], pointDic);
            FindRationalPath(pointDic[1], pointDic);
            Console.WriteLine(rationalPathCount);
        }
        private void FindPath(PointInfo pointNow, Dictionary<int, PointInfo> pointDic)
        {
            foreach (int index in pointNow.Path.Keys)
            {
                int beforeLength = pointDic[index].LengthToEnd;
                int newLength = pointNow.LengthToEnd + pointNow.Path[index];
                if (newLength < beforeLength)
                {
                    pointDic[index].LengthToEnd = newLength;
                    if (index != 1)
                    {
                        FindPath(pointDic[index], pointDic);
                    }
                }
            }
        }
        private void FindRationalPath(PointInfo pointNow, Dictionary<int, PointInfo> pointDic)
        {
            foreach (int index in pointNow.Path.Keys)
            {
                if (pointDic[index].LengthToEnd < pointNow.LengthToEnd)
                {
                    if (index == 2)
                    { rationalPathCount++; }
                    else
                    { FindRationalPath(pointDic[index], pointDic); }
                }
            }
        }
    }
    class PointInfo
    {
        private Dictionary<int, int> _path = new Dictionary<int, int>();
        public Dictionary<int, int> Path { get { return _path; } }
        private int _lengthToEnd = int.MaxValue;
        public int LengthToEnd { get { return _lengthToEnd; } set { _lengthToEnd = value; } }

        public PointInfo()
        {
        }
        public void AddPath(int index, int length)
        {
            if (!Path.Keys.Contains(index))
            {
                Path.Add(index, length);
            }
        }

    }
}
